import java.util.ArrayList;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 129. 求根节点到叶节点数字之和
 * @author: WXY
 * @create: 2023-02-12 12:21
 * @Version 1.0
 **/
public class Num129_sumNumbers {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static int sumNumbers1(TreeNode root) {
        Info ans = process(root);
        return ans.sumNum;
    }

    private static Info process(TreeNode root) {
        if (root == null) {
            return new Info(null, 0, 0);
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        List<Integer> curList = new ArrayList<>();
        if (leftInfo.list == null && rightInfo.list == null) curList.add(root.val);
        if (leftInfo.list != null && root.left.val != 0) {
            addList(leftInfo.list, curList, root.val);
        }
        if (rightInfo.list != null && root.right.val != 0) {
            addList(rightInfo.list, curList, root.val);
        }
        int sumNum = 0;
        if (root.left != null && root.left.val == 0) {
            if (root.left.val == 0 && leftInfo.sumNum == 0) {
                int num = (int) (root.val * Math.pow(10, leftInfo.height));
                curList.add(num);
            } else if (root.val == 0 && leftInfo.sumNum != 0) {
                int num = (int) (root.val * Math.pow(10, leftInfo.height));
                curList.add(num);
                sumNum = leftInfo.sumNum;
            }
        }
        if (root.right != null && root.right.val == 0) {
            if (rightInfo.sumNum == 0) {
                int num = (int) (root.val * Math.pow(10, rightInfo.height));
                curList.add(num);
            } else {
                sumNum = rightInfo.sumNum;
            }
        }

        for (int num : curList) {
            sumNum += num;
        }
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(curList, sumNum, height);
    }

    private static void addList(List<Integer> list, List<Integer> curList, int val) {
        for (int num : list) {
            int bit = countBit(num);
            int curNum = (int) (val * Math.pow(10, bit)) + num;
            curList.add(curNum);
        }
    }

    private static int countBit(int num) {
        if (num == 0) return 1;
        int bit = 0;
        while (num > 0) {
            num /= 10;
            bit++;
        }
        return bit;
    }

    public static class Info {
        List<Integer> list;
        int height;
        int sumNum;

        public Info(List<Integer> list, int sumNum, int height) {
            this.list = list;
            this.height = height;
            this.sumNum = sumNum;
        }
    }


    public static List<Integer> path = new ArrayList<Integer>();
    static int ans = 0;
    public static int sumNumbers(TreeNode root) {
        if (root == null )return 0;
        path.add(root.val);
        recur(root);
        return ans;
    }

    private static void recur(TreeNode root) {
        if (root.left == null && root.right == null) {
            ans += listToInt(path);
            return;
        }
        if (root.left != null) {
            path.add(root.left.val);
            recur(root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            recur(root.right);
            path.remove(path.size() - 1);
        }
        return;
    }

    private static int listToInt(List<Integer> path) {
        int sum = 0;
        for (int num : path) {
            sum = sum * 10 + num;
        }
        return sum;
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(0);
        head.right = new TreeNode(0);
        head.right.left = new TreeNode(3);
        head.right.left.left = new TreeNode(5);
        head.right.left.left.left = new TreeNode(8);
        head.right.left.left.left.left = new TreeNode(7);
        int num = sumNumbers(head);
        System.out.println(num);

    }
}
